PHASE6: Build traversal clusters based HighOrder2 graph

Summary
Based on HightOrder2 node/edge graph from PHASE5, this phase identifies intersecting paths to create disjointed (or size-limited) nodes/edges into clusters. Then identifies, nearby clusters and link them. Finally, a new cluster_node/cluster_edge based graph would be created which would be further longer and sparser.

STEP11a: Identifying the traversal clusters among node_highorder2
Nodes (node_highorder2) form islands of 'clusters' due to intersecting edges. We will identify them and then link those islands

Ref: C:\GangaToKaveri\docs\g2k_contracted_shortcut_edges_linked_with_islands.png

TRUNCATE TABLE traversal_clusters_rownum_highorder2, traversal_clusters_highorder2;

ALTER SEQUENCE traversal_clusters_highorder2_cluster_id_seq RESTART WITH 1;

Config Parameters:
WARNING executionPartitions must be decided before starting the batch runs -- as context state is maintained based on this value
executionPartitions sets number of concurrent threads run at a time
dbConnectionInitSql is set specific for clustering activities with large work-memory and timeout

Initialize clustering process state:
${PCH_APP_HOME}/run_G2KContractedEdgeClusterer.sh --action resetTraversalClusterStateHighOrder2 --yesIReallyWantToDo true
NOTE:
This step will truncate the traversal_clusters_highorder2 table -- no need to manually truncate it.

Run the clustering process:
nohup ${PCH_APP_HOME}/run_G2KContractedEdgeClusterer.sh --action runTraversalClusteringHighOrder2 > $PCH_LOG_HOME/nohup.out 2>&1 &
NOTE:
For 58871942 highorder2 nodes, runs with ~20% per hour for ~6 hours -- generating ~8422986 clusters

SELECT COUNT(*) FROM traversal_clusters_highorder2;

Returns:
35675713

Returns:
  count
---------
 35675713

SELECT MIN(CARDINALITY(from_node_ids)), MAX(CARDINALITY(from_node_ids)), MIN(CARDINALITY(to_node_ids)), MAX(CARDINALITY(to_node_ids)),
MIN(CARDINALITY(node_ids)), MAX(CARDINALITY(node_ids)) FROM traversal_clusters_highorder2;

Returns:
 min | max | min | max | min | max
-----+-----+-----+-----+-----+-----
   0 |   7 |   0 |   1 |   2 |  64

Returns:
 min | max | min | max | min | max
-----+-----+-----+-----+-----+-----
   0 |   7 |   0 |   1 |   2 |  64

Analyze initial clusters:
SET statement_timeout = 9600000; SET lock_timeout=1200000; SET work_mem TO '2048MB';
SELECT 100 AS batch_size, -1 AS starting_cluster_id \gset
CALL g2k_build_traversal_cluster_geom_highorder2(0, 20, :batch_size, :starting_cluster_id, true);
CALL g2k_build_traversal_cluster_geom_highorder2(20, 40, :batch_size, :starting_cluster_id, true);
CALL g2k_build_traversal_cluster_geom_highorder2(40, 60, :batch_size, :starting_cluster_id, true);
CALL g2k_build_traversal_cluster_geom_highorder2(60, 80, :batch_size, :starting_cluster_id, true);
CALL g2k_build_traversal_cluster_geom_highorder2(80, 101, :batch_size, :starting_cluster_id, true); -- intentionally larger than 100%

NOTE:
You can parallelize using multiple sessions
Runs for 4hrs

SELECT clstr.cluster_id, ST_Length(ST_LongestLine(clstr.from_to_box, clstr.from_to_box)) AS max_length
FROM traversal_clusters_geom_highorder2 AS clstr
ORDER BY max_length DESC LIMIT 5;

Returns:
cluster_id | max_length
------------+----------------------
15515799 | 0.03531712591245387
32719722 | 0.031122269824233995
28119776 | 0.031052772683901518
31716581 | 0.030877096070200116
21199330 | 0.030681558381075374
NOTE: longest cluster polygon is 0.0353*100=3.53km long -- reasonable to expect (comparable to 0.2392 of edge_highorder2) at initial stage before merging the overlaps

REVIEW
Using QGIS, view traversal_clusters_geom_highorder2.from_to_box and from_to_lines by filtering for cluster_id: 356976,341733,511171,651245,51518
NOTE:
Make sure that individual clusters are NOT disjoint (from_to_box doest NOT contain multiple segments of from_to_lines)

Ref: C:\GangaToKaveri\docs\g2k_on_osm_line_with_island_clusters_only.png

STEP11b: Merging the overlapping traversal clusters
Build cluster-node/edge based on traversal cluster :
cluster forms node and overlapping node_ids across clusters forms edge

SET statement_timeout=1800000;
SELECT 1000 AS batch_size, -1 AS starting_cluster_id \gset
CALL g2k_build_graph_for_merge_clusters_stage1(-1, 101, :batch_size, :starting_cluster_id, true); -- truncates cluster node/edge
CALL g2k_build_graph_for_merge_clusters_stage1(0, 20, :batch_size, :starting_cluster_id, true);
CALL g2k_build_graph_for_merge_clusters_stage1(20, 40, :batch_size, :starting_cluster_id, true);
CALL g2k_build_graph_for_merge_clusters_stage1(40, 60, :batch_size, :starting_cluster_id, true);
CALL g2k_build_graph_for_merge_clusters_stage1(60, 80, :batch_size, :starting_cluster_id, true);
CALL g2k_build_graph_for_merge_clusters_stage1(80, 95, :batch_size, :starting_cluster_id, true); -- intentionally stopped at 95%
--~~~~ RUN below last batch AFTER ALL ABOVE batches were completed ~~~~__
CALL g2k_build_graph_for_merge_clusters_stage1(95, 101, :batch_size, :starting_cluster_id, true); -- intentionally larger than 100%
--~~~~ RUN above last batch AFTER ALL ABOVE batches were completed ~~~~__
NOTE:
Do not parallelize using multiple sessions -- as above steps write too much too quicky on single table
Run the last batch --- ONLY AFTER --- confirming that all other batches are completed -- as the last batch builds cluter_node table
Runs for 20min

Partition traversal cluster by reachability through cluster-node/edge (Populating: traversal_cluster_partition_highorder2)

Config Params:
mergeTraversalClusterPartitionCapMin sets the lower-limit to number of clusters before mergeTraversalClusterPartitionDistCapKm condition applied (every 1000 new clusters)
mergeTraversalClusterPartitionDistCapKm means cluster merging would be stopped/capped when size of partition (longest distance) exceeds this. It is selected to be > 10 times longest cluster polygon (1.92km on DEV; 2.52 on B2Y)
mergeTraversalClusterPartitionCap sets the upper-limit to number of clusters included to a patition. This is set to avoid super-mega clusters
mergeTraversalClusterPartitionCap is selected to be 2500 -- based on longest cluster polygon (1.92km 2000m on DEV; 2.52 on B2Y);
even if each cluster contributes 0.1% length (2m) to partition, 2500 clusters would make the largest cluster-partition to be 25km long on DEV; 30km on B2Y
Increasing this limit would make largest cluster-partition longer
fetchBatchSize is reduced to 2000 -- since traversal_cluster_partition_highorder2's cluster_ids column gets very large

nohup ${PCH_APP_HOME}/run_G2KTraversalClusterPartition.sh --action runTraversalClusterPartitionHighOrder2 > $PCH_LOG_HOME/nohup.out 2>&1 &
NOTE:
Process runs slow in the beginning -- since there is no existing partitions
Runs for 4days creating ~247534 partitions (out of 35675713 clusters -- 99.3% reduction)

SELECT COUNT(*) FROM traversal_cluster_partition_highorder2;

    Returns:
     count
    --------
     247534		247534/35675713=0.693%

    Returns:
     count
    --------
     247534		247534/35675713=0.693%

Fill edge-nodes per each parition
NOTE:
The paritions identified by reachability through cluster-node/edge need to be filled with all the ingress and egress edge nodes of traversal-clusters
Since partitioning is done starting from arbitrary point and done progressively, there are chances that some partition clusters do not have any from-nodes and/or to-nodes
This step will fill up with some from-nodes and/or to-nodes to each cluster

SET statement_timeout = 9600000; SET lock_timeout=1200000; SET work_mem TO '2048MB';
SELECT 50 AS batch_size, 1000 AS max_nodes_to_add, -1 AS starting_partition \gset
\set log_trace true
CALL g2k_fill_traversal_cluster_part_edgenodes(0, 25, :batch_size, :max_nodes_to_add, :starting_partition, :log_trace);
CALL g2k_fill_traversal_cluster_part_edgenodes(25, 50, :batch_size, :max_nodes_to_add, :starting_partition, :log_trace);
CALL g2k_fill_traversal_cluster_part_edgenodes(50, 75, :batch_size, :max_nodes_to_add, :starting_partition, :log_trace);
CALL g2k_fill_traversal_cluster_part_edgenodes(75, 100, :batch_size, :max_nodes_to_add, :starting_partition, :log_trace);

NOTE:
You may parallelize using few (1/2) sessions
It runs for ~30min
SELECT COUNT(*) AS total_missing FROM traversal_cluster_partition_highorder2 WHERE from_node_ids IS NULL OR CARDINALITY(from_node_ids) = 0;

Returns:
 total_missing
---------------
          0

Returns:
 total_missing
---------------
          0

SELECT COUNT(*) AS total_missing FROM traversal_cluster_partition_highorder2 WHERE to_node_ids IS NULL OR CARDINALITY(to_node_ids) = 0;

Returns:
 total_missing
---------------
         6674

Returns:
 total_missing
---------------
         6674

SELECT MIN(CARDINALITY(from_node_ids)) AS min_fromnodes,MAX(CARDINALITY(from_node_ids)) AS max_fromnodes,
MIN(CARDINALITY(to_node_ids)) AS min_tonodes,MAX(CARDINALITY(to_node_ids)) AS max_tonodes,
MIN(CARDINALITY(node_ids)) AS min_nodes,MAX(CARDINALITY(node_ids)) AS max_nodes
FROM traversal_cluster_partition_highorder2;

Returns:
 min_fromnodes | max_fromnodes | min_tonodes | max_tonodes | min_nodes | max_nodes
---------------+---------------+-------------+-------------+-----------+-----------
             1 |            73 |           1 |        1000 |         2 |      5475

Returns:
 min_fromnodes | max_fromnodes | min_tonodes | max_tonodes | min_nodes | max_nodes
---------------+---------------+-------------+-------------+-----------+-----------
             1 |            73 |           1 |        1000 |         2 |      5475

WARNING
For partition containing ~5400 nodes, the from-node count of 73 is very small.
We should use partition's boundary polygon to identify egress edges to identity more from-nodes

Build partition's boundary polygons
The partition's boundary polygons will be used to identify more from-nodes that are nodes of edges that are ingress to the polygon

SET statement_timeout = 9600000; SET lock_timeout=1200000; SET work_mem TO '2048MB';
SELECT 100 AS batch_size, -1 AS starting_partition \gset
\set log_trace true
CALL g2k_build_travrslclstr_part_geom_highorder2(-1, 101, :batch_size, :starting_partition, :log_trace); -- truncates traversal_cluster_partition_geom_highorder2
CALL g2k_build_travrslclstr_part_geom_highorder2(0, 25, :batch_size, :starting_partition, :log_trace); -- will be too slow
CALL g2k_build_travrslclstr_part_geom_highorder2(25, 50, :batch_size, :starting_partition, :log_trace);
CALL g2k_build_travrslclstr_part_geom_highorder2(50, 75, :batch_size, :starting_partition, :log_trace);
CALL g2k_build_travrslclstr_part_geom_highorder2(75, 100, :batch_size, :starting_partition, :log_trace);

NOTE:
You may parallelize using few (1/2) sessions

Analyze partition's boundary polygons:
SELECT part.partition, ST_Length(ST_LongestLine(part.from_to_box, part.from_to_box)) AS max_length
FROM traversal_cluster_partition_geom_highorder2 AS part
ORDER BY max_length DESC LIMIT 5;

Returns:
 partition |     max_length
-----------+---------------------
     31134 | 0.28087852697131643
     19857 |  0.2689970512482408
     12682 |  0.2682408685868886
     42710 |  0.2636134527468903
     84374 | 0.26083865809261825

Returns:
 partition |     max_length
-----------+---------------------
     31134 | 0.28087852697131643
     19857 |  0.2689970512482408
     12682 |  0.2682408685868886
     42710 |  0.2636134527468903
     84374 | 0.26083865809261825

NOTE: Partitions are as large as 28.08lm -- comparable to cluster sizes

SELECT COUNT(part.partition)
FROM traversal_cluster_partition_geom_highorder2 AS part
WHERE ST_Length(ST_LongestLine(part.from_to_box, part.from_to_box)) > 0.15;

Returns:
 count
-------
 12900

Returns:
 count
-------
 12900

NOTE:
4.8% (12900/295515) partitions are larger than 15km

Include ingress edges to from-nodes of partitions
NOTE: Using partition's boundary polygons we identify the edges (as line between from-and-to nodes), that cross into polygon -- to find from-nodes and to-nodes

SET statement_timeout = 9600000; SET lock_timeout=1200000; SET work_mem TO '2048MB';
SELECT 100 AS max_from_nodes_to_add \gset
CALL g2k_add_travrslclstr_part_xngnodes_highorder2(0, 25, :max_from_nodes_to_add); -- will be too slow
CALL g2k_add_travrslclstr_part_xngnodes_highorder2(25, 50, :max_from_nodes_to_add);
CALL g2k_add_travrslclstr_part_xngnodes_highorder2(50, 75, :max_from_nodes_to_add);
CALL g2k_add_travrslclstr_part_xngnodes_highorder2(75, 100, :max_from_nodes_to_add);

NOTE:
You may parallelize using few (1/2) sessions

Returns:
 min_fromnodes | max_fromnodes | min_tonodes | max_tonodes | min_nodes | max_nodes
---------------+---------------+-------------+-------------+-----------+-----------
             1 |           100 |           1 |        1000 |         2 |      5651

Returns:
 min_fromnodes | max_fromnodes | min_tonodes | max_tonodes | min_nodes | max_nodes
---------------+---------------+-------------+-------------+-----------+-----------
             1 |           100 |           1 |        1000 |         2 |      5651

NOTE:
For partition containing ~5600 nodes, the from-node count got increased from 44/73 to 100 (all-nodes from 5417 to 5632)

Split too-wide partitions (Populating: traversal_cluster_subpartition_highorder2)
NOTE: The from-nodes of the clusters of each partition are going to be analyzed to see if they form geographical groups --
the nodes that are very far away from each other would be in different groups. Then, partition would be split into multiple partitions --
containing one from-node group each. This will make each partition to contain only geographically near-by from-nodes.

TRUNCATE TABLE traversal_cluster_subpartition_highorder2;

SET statement_timeout = 9600000; SET lock_timeout=1200000; SET work_mem TO '2048MB';
SELECT 0.02 AS subpart_dist_tolerence, 100 AS batch_size, -1 AS starting_partition \gset

CALL g2k_build_traversal_cluster_subpartition(0, 25, :subpart_dist_tolerence, :batch_size, :starting_partition, true); -- will be too slow
CALL g2k_build_traversal_cluster_subpartition(25, 50, :subpart_dist_tolerence, :batch_size, :starting_partition, true);
CALL g2k_build_traversal_cluster_subpartition(50, 75, :subpart_dist_tolerence, :batch_size, :starting_partition, true);
CALL g2k_build_traversal_cluster_subpartition(75, 100, :subpart_dist_tolerence, :batch_size, :starting_partition, true);

NOTE:
subpart_dist_tolerence is set to 0.04: the from-nodes that are near-by the distance <= 4km are considered to be part of same sub-partition
Since some partitioning is skewed (~300 partitions have > 10000 clusters), the batch_size is set to 200.
First few batches would be very slow due to skewed numbers
No need to parallelize. It runs for ~15min

SELECT COUNT(*) FROM traversal_cluster_partition_highorder2;

Returns:
 count
--------
 295515

Returns:
 count
--------
 295515

SELECT COUNT(*) FROM traversal_cluster_subpartition_highorder2;

Returns:
 count
--------
 295515

Returns:
 count
--------
 384169

<<Added ~34% new sub-partitions ((384169-295515)/295515)>>

SELECT MIN(CARDINALITY(from_node_ids)) AS min_fromnodes,MAX(CARDINALITY(from_node_ids)) AS max_fromnodes
FROM traversal_cluster_subpartition_highorder2;

Returns:
 min_fromnodes | max_fromnodes
---------------+---------------
             1 |           100

Returns:
 min_fromnodes | max_fromnodes
---------------+---------------
             1 |           100

SELECT sub_partition, COUNT(*) FROM traversal_cluster_subpartition_highorder2 GROUP BY sub_partition ORDER BY sub_partition;

Returns:
 sub_partition | count
---------------+--------
             0 | 295515
             1 |  15185
             2 |   8691
             3 |   4391
             4 |   1901
             5 |    702
             6 |    251
             7 |     82
             8 |     24
             9 |      8
            10 |      1

Returns:
 sub_partition | count
---------------+--------
             0 | 295515
             1 |  15185
             2 |   8691
             3 |   4391
             4 |   1901
             5 |    702
             6 |    251
             7 |     82
             8 |     24
             9 |      8
            10 |      1

Extend each traversal cluster sub-partition with nearby nodes
NOTE: The from-nodes of sub-partition are too little. Hence we will promote nearby nodes within the partition as from-nodes -- so that all subpartitions together will reach all nodes of partition
On PROD/B2Y/DEV:
SET statement_timeout = 9600000; SET lock_timeout=1200000; SET work_mem TO '2048MB';
SELECT 0.01 AS max_nearby_distance, 100 AS batch_size, -1 AS starting_partition \gset
CALL g2k_extend_traversal_cluster_subpartition(0, 25, :max_nearby_distance, :batch_size, :starting_partition, true);
CALL g2k_extend_traversal_cluster_subpartition(25, 50, :max_nearby_distance, :batch_size, :starting_partition, true);
CALL g2k_extend_traversal_cluster_subpartition(50, 75, :max_nearby_distance, :batch_size, :starting_partition, true);
CALL g2k_extend_traversal_cluster_subpartition(75, 100, :max_nearby_distance, :batch_size, :starting_partition, true);
NOTE:
max_nearby_distance is set to 0.01: the nodes within partition that are near-by to a from-node by the distance <= 0.25km are considered to be member of from-nodes
You can parallelize using multiple sessions
It runs for ~75min

SELECT MIN(CARDINALITY(from_node_ids)), MAX(CARDINALITY(from_node_ids))
FROM traversal_cluster_subpartition_highorder2;

Returns:
 min | max
-----+------
   1 | 4593

Returns:
 min | max
-----+------
   1 | 4593

NOTE:
The count of from_node_ids got increased forty-fold (from 100 to 4593)
Re-create traversal clusters for each sub-partition

Config Params:
fetchBatchSize is set to 100 -- since traversal_cluster_partition_highorder2's node_ids column gets very large for some cluster-partitions
executionPartitions is set to 24

nohup ${PCH_APP_HOME}/run_G2KTraversalClusterPartition.sh --action runBuiltSubpartitionTraversalClusterHighOrder2 > $PCH_LOG_HOME/nohup.out 2>&1 &

NOTE:
Process runs slow in the beginning -- since there is no existing partitions
Runs for ~75min

Review merged traversal clusters

SELECT MIN(from_node_cnt), MAX(from_node_cnt), MIN(to_node_cnt), MAX(to_node_cnt),MIN(node_cnt), MAX(node_cnt) FROM traversal_clusters_highorder2;

Returns:
 min | max  | min | max  | min | max
-----+------+-----+------+-----+------
   1 | 4571 |   1 | 2962 |   1 | 5021

Returns:
 min | max  | min | max  | min | max
-----+------+-----+------+-----+------
   1 | 4571 |   1 | 2962 |   1 | 5021

Result of merged cluster is:

Ref: C:\GangaToKaveri\docs\g2k_large_clusters_between__yamuna_and_narmada__05172025.png

Analyze merged clusters:
SELECT clstr.cluster_id, ST_Length(ST_LongestLine(clstr.from_to_box, clstr.from_to_box)) AS max_length
FROM traversal_clusters_geom_highorder2 AS clstr
ORDER BY max_length DESC LIMIT 5;

SELECT COUNT(clstr.cluster_id)
FROM traversal_clusters_geom_highorder2 AS clstr
WHERE ST_Length(ST_LongestLine(clstr.from_to_box, clstr.from_to_box)) > 0.5;

Returns:
 cluster_id |     max_length
------------+---------------------
      15557 | 0.23954448155192024
      19555 | 0.23630270004674822
      31356 | 0.23292358202150398
       4100 | 0.23232752795765432
       4101 | 0.23209459544454447

Returns:
 cluster_id |     max_length
------------+---------------------
      15557 | 0.23954448155192024
      19555 | 0.23630270004674822
      31356 | 0.23292358202150398
       4100 | 0.23232752795765432
       4101 | 0.23209459544454447

NOTE:
Longest cluster polygon is 0.2395*100=23.95km long

STEP11d: Update traversal cluster's node-reference (1st level) and node-point locations:
SET statement_timeout=1800000;
CALL g2k_set_traversal_cluster_noderefs_highorder2(0, 20);
CALL g2k_set_traversal_cluster_noderefs_highorder2(20, 40);
CALL g2k_set_traversal_cluster_noderefs_highorder2(40, 60);
CALL g2k_set_traversal_cluster_noderefs_highorder2(60, 80);
CALL g2k_set_traversal_cluster_noderefs_highorder2(80, 100);

NOTE:
You can parallelize using multiple sessions

Re-Build linestring and bounding-box geometries of traversal clusters:
SELECT 100 AS batch_size, -1 AS starting_cluster_id \gset
CALL g2k_build_traversal_cluster_geom_highorder2(0, 20, :batch_size, :starting_cluster_id, true); -- will be too slow
CALL g2k_build_traversal_cluster_geom_highorder2(20, 40, :batch_size, :starting_cluster_id, true);
CALL g2k_build_traversal_cluster_geom_highorder2(40, 60, :batch_size, :starting_cluster_id, true);
CALL g2k_build_traversal_cluster_geom_highorder2(60, 80, :batch_size, :starting_cluster_id, true);
CALL g2k_build_traversal_cluster_geom_highorder2(80, 100, :batch_size, :starting_cluster_id, true);

NOTE:
You can parallelize using multiple sessions

Rearrange traversal clusters' from-nodes and to-nodes to be ordered by locationgrp:
CALL g2k_reorder_traversal_cluster_nodes_highorder2(0, 20); -- will be too slow
CALL g2k_reorder_traversal_cluster_nodes_highorder2(20, 40);
CALL g2k_reorder_traversal_cluster_nodes_highorder2(40, 60);
CALL g2k_reorder_traversal_cluster_nodes_highorder2(60, 80);
CALL g2k_reorder_traversal_cluster_nodes_highorder2(80, 100);

NOTE:
You can parallelize using multiple sessions

Analyze post-merged clusters:
SELECT clstr.cluster_id, ST_Length(ST_LongestLine(clstr.from_to_box, clstr.from_to_box)) AS max_length
FROM traversal_clusters_geom_highorder2 AS clstr
ORDER BY max_length DESC LIMIT 5;
cluster_id | max_length
------------+---------------------
15557 | 0.23954448155192024
19555 | 0.23630270004674822
31356 | 0.23292358202150398
4100 | 0.23232752795765432
4101 | 0.23209459544454447

NOTE: The result should not have changed much between STEP 11b and 11d

STEP11f: Populating nearest_traversal_clusters by nearby disjointed traversal clusters
NOTE nearest_traversal_clusters is used by "Linking neighborhood traversal clusters" tasks

SELECT cluster_id,initial_node_id,node_cnt FROM traversal_clusters_highorder2 ORDER BY node_cnt DESC LIMIT 10;

Results:
 cluster_id |  initial_node_id   | node_cnt
------------+--------------------+----------
      27881 |  65999221554600019 |     4997
      11325 |  82422750616400902 |     4968
     130989 | 831175910369500018 |     4954
      74865 |  65516525134100940 |     4936
       8315 |  15768750461300462 |     4858
     294850 | 832831726366800300 |     4839
      26464 |  16514081466100473 |     4829
      11300 |  65507920615200343 |     4821
     139340 | 663611611162600740 |     4796
      59984 |  64238293861000124 |     4782

Results:
 cluster_id |  initial_node_id   | node_cnt
------------+--------------------+----------
      27881 |  65999221554600019 |     4997
      11325 |  82422750616400902 |     4968
     130989 | 831175910369500018 |     4954
      74865 |  65516525134100940 |     4936
       8315 |  15768750461300462 |     4858
     294850 | 832831726366800300 |     4839
      26464 |  16514081466100473 |     4829
      11300 |  65507920615200343 |     4821
     139340 | 663611611162600740 |     4796
      59984 |  64238293861000124 |     4782

NOTE:
Largest clusters have ~5000 nodes.
Since there is not cluster having > 250000 nodes, we will disable super-mega-clusters

SELECT COUNT(cluster_id) FROM traversal_clusters_highorder2 WHERE node_cnt >= 20000;

Results:
count
-------
       0

Results:
count
-------
       0

SELECT COUNT(cluster_id) FROM traversal_clusters_highorder2 WHERE node_cnt >= 2000;

Results:
 count
-------
  11247

Results:
 count
-------
  11247

NOTE:
ON PROD, Since < 3.8% of clusters (11247/295515) have > 2000 nodes, we will use 2000 as mega-cluster setting

SELECT COUNT(cluster_id) FROM traversal_clusters_highorder2 WHERE node_cnt < 5000 AND node_cnt >= 4000;

Results:
 count
-------
   920

Results:
 count
-------
   920

SELECT COUNT(cluster_id) FROM traversal_clusters_highorder2 WHERE node_cnt < 4000 AND node_cnt >= 2000;

Results:
 count
-------
  10327

Results:
 count
-------
  10327

NOTE:
Clusters having > 15000 nodes are super-mega and having > 3000 nodes are mega clusters. This will be applied to nodesInSuperMegaClusters below
If there were super-mega clusters, they will be handled separately and manually

SELECT 2000 AS mega_cluster_nodes \gset
TRUNCATE TABLE traversal_clusters_mega_highorder2;
INSERT INTO traversal_clusters_mega_highorder2 (cluster_id, node_cnt)
SELECT cluster_id, node_cnt FROM traversal_clusters_highorder2 WHERE node_cnt >= :mega_cluster_nodes;

Identify and create nearest clusters to link

Config Params:
Set nearestClusteredShortcutsToLink/nearestClusteredShortcutsToLinkHighOrder for number of nearest clusters to be associated
If too many clusters of small sizes (~20km/ < 5000 nodes) were created then set this to large number (8 -- instead of 6)
executionPartitions set it NOT to exceed the CPU cores of the DB server -- to avoid thrashing
WARNING executionPartitions must be decided before starting the batch runs -- as context state is maintained based on this value
maxNearbyDistanceKm is used to limit nodes in each clusters to consider for intra-cluster linking
nodesInSuperMegaClusters tells the process to exclude them using standard process and will be handled separately -- as they cause session timeouts
nodesInMegaClusters tells the process which cluster would be considered as mega clusters (and hence all other clusters contained by them are considered nearest to them)
buildNearestTraversalClustersMaxPerNode defines maximum nearby clusters are linked to same single node (so that nearby clusters are picked all around a cluster)
Set buildNearestTraversalClustersBatchPercentile, buildNearestTraversalClustersBatchSize and statement_timeout appropriately to avoid batch failures
If cluster partition is very highly skewed, then reduce BatchPercentile and BatchSize
Set nearestClusteredShortcutsToLinkHighOrder for number of nearest clusters to be associated
work_mem in dbConnectionInitSql is increased to 1.5GB to avoid error like: "LOG: temporary file: path "base/pgsql_tmp/pgsql_tmp9732.12", size 1073741824"

Initialize nearest clustering process state:
${PCH_APP_HOME}/run_G2KContractedEdgeClusterer.sh --action resetNearestTraversalClusterStateHighOrder2 --yesIReallyWantToDo true

Run the nearest clustering process:
The runNearestTraversalClustering step creates association from-cluster to nearby to-cluster for every edge outward nodes:

nohup ${PCH_APP_HOME}/run_G2KContractedEdgeClusterer.sh --action runNearestTraversalClusteringHighOrder2 > $PCH_LOG_HOME/nohup.out 2>&1 &

NOTE:
runNearestTraversalClustering handles all the clusters -- including super-mega clusters
Totally, 1034678 rows are added out of 295515 traversal_clusters_highorder2 rows in 18hrs

Analyze nearby clusters:
SELECT COUNT(*) FROM nearest_traversal_clusters_highorder2;

Results:
  count
---------
 1683971

Results:
  count
---------
 1683971

SELECT COUNT(DISTINCT from_cluster_id) AS total_from FROM nearest_traversal_clusters_highorder2;

Results:
 total_from
------------
     282774	(95.68% 282774/295515)

Results:
 total_from
------------
     282774	(95.68% 282774/295515)

WARNING This should be very close to total traversal clusters -- close by 90%

SELECT COUNT(DISTINCT to_cluster_id) AS total_to FROM nearest_traversal_clusters_highorder2;

Results:
 total_to
----------
   294659	(99.71% 294659/295515)

Results:
 total_to
----------
   294659	(99.71% 294659/295515)

WARNING This should be very close to total traversal clusters -- close by 95%

SELECT COUNT(*) FROM nearest_traversal_clusters_highorder2 WHERE distance = 0;

Results:
 count
-------
 67040

Results:
 count
-------
 67040

NOTE: These are for overlapping clusters

STEP11g: Update nearest cluster's node ids and geo location details
SET statement_timeout = 9600000; SET lock_timeout=1200000; SET work_mem TO '2048MB';

PROD: SELECT 500 AS batch_size, 0.06 AS max_nearby_distance \gset
CALL g2k_update_nearest_traversal_clusters_highorder2(0, 25, :batch_size, :max_nearby_distance, true);
CALL g2k_update_nearest_traversal_clusters_highorder2(25, 50, :batch_size, :max_nearby_distance, true);
CALL g2k_update_nearest_traversal_clusters_highorder2(50, 75, :batch_size, :max_nearby_distance, true);
CALL g2k_update_nearest_traversal_clusters_highorder2(75, 100, :batch_size, :max_nearby_distance, true);

NOTE:
You could parallelize the above calls from multiple sessions

With four sessions, 100 percentiles are completed in 4hours

Analyze first-stage of nearby updates:
SELECT link_id,from_cluster_id,to_cluster_id,distance FROM nearest_traversal_clusters_highorder2 ORDER BY distance DESC LIMIT 5;
link_id | from_cluster_id | to_cluster_id | distance
---------+-----------------+---------------+----------------------
5651991 | 91245 | 145072 | 0.05110884656819068
5827682 | 235428 | 138132 | 0.044462669874241086
5860055 | 236048 | 179469 | 0.04441405210843946
5652015 | 91245 | 240214 | 0.044037196679148564
5652001 | 91245 | 180703 | 0.04240093756242663

NOTE:
Distance should not have changed too much from previous check (could get lesser than before)

Delete nearest traversal cluster that is linking egress-to-egress edges:
(If egress-to-egress edges are found, no further routing can happen through new link)

CALL CALL g2k_remove_e2e_nearest_traversal_clusters_highorder2(true);
<<DELETE 31798>>
NOTE:
For overlapping clusters, above task would have > 0 rows deleted. If all clusters are disjointed, there won't be anything to delete.

Removing dangling nearest traversal cluster relations:
${PCH_APP_HOME}/run_G2KContractedEdgeClusterer.sh --action runFinalizeNearestTraversalClustersHighOrder2

NOTE: runs for 5sec.

Verify that there are enough nearest clusters:
SELECT COUNT(clst.from_cluster_id) FROM
(SELECT from_cluster_id, COUNT(from_cluster_id) AS counts
FROM nearest_traversal_clusters_highorder2 WHERE distance > 0 GROUP BY from_cluster_id) AS clst
WHERE clst.counts <= 1;

<<Returns: 43433 -- 2.6% out of 1651287>>

NOTE: If count is too large, then redo whole task with higher nearestClusteredShortcutsToLink in runtime_cost_spec_by_db.json

STEP11h: Optionally Trimming far-away neighbors
SELECT ROUND((distance100)::numeric, 1) AS dist,COUNT(ROUND((distance100)::numeric, 1)) FROM nearest_traversal_clusters_highorder2 GROUP BY dist ORDER BY dist;

Ref: C:\GangaToKaveri\docs\g2k_traversal_nearest_cluster_by_distance.xlsx
NOTE:
Only 10.9% (111654/1017503) of neighbor clusters are more than 2.6km away [0.81% (8265/1017503) of neighbor clusters are more than 4.5km away]
If this percentage is too much, then procede for trimming. Else, skip this step from here.

\set distance_to_limit 0.015
WITH total_clusters AS (
select COUNT(DISTINCT from_cluster_id) AS from_count, COUNT(DISTINCT to_cluster_id) AS to_count FROM nearest_traversal_clusters_highorder2
), neighbors AS (
select COUNT(DISTINCT from_cluster_id) AS from_cluster, COUNT(DISTINCT to_cluster_id) AS to_cluster
FROM nearest_traversal_clusters_highorder2 WHERE distance <= :distance_to_limit
)
SELECT neighbors.from_cluster AS from_clusters, 100.0neighbors.from_cluster/total_clusters.from_count AS from_cluster_pct,
neighbors.to_cluster AS to_clusters, 100.0neighbors.to_cluster/total_clusters.to_count AS to_cluster_pct
FROM total_clusters, neighbors;

\set distance_to_limit 0.015
 from_clusters |  from_cluster_pct   | to_clusters |   to_cluster_pct
---------------+---------------------+-------------+---------------------
        270869 | 99.8223702879296557 |      293790 | 99.7101586999904970
\set distance_to_limit 0.02
 from_clusters |  from_cluster_pct   | to_clusters |   to_cluster_pct
---------------+---------------------+-------------+---------------------
        271322 | 99.9893127351658921 |      294555 | 99.9697940565563867
\set distance_to_limit 0.03
 from_clusters |   from_cluster_pct   | to_clusters |    to_cluster_pct
---------------+----------------------+-------------+----------------------
        271351 | 100.0000000000000000 |      294644 | 100.0000000000000000

\set distance_to_limit 0.015
 from_clusters |  from_cluster_pct   | to_clusters |   to_cluster_pct
---------------+---------------------+-------------+---------------------
        270869 | 99.8223702879296557 |      293790 | 99.7101586999904970
\set distance_to_limit 0.02
 from_clusters |  from_cluster_pct   | to_clusters |   to_cluster_pct
---------------+---------------------+-------------+---------------------
        271322 | 99.9893127351658921 |      294555 | 99.9697940565563867
\set distance_to_limit 0.03
 from_clusters |   from_cluster_pct   | to_clusters |    to_cluster_pct
---------------+----------------------+-------------+----------------------
        271351 | 100.0000000000000000 |      294644 | 100.0000000000000000

More than 99.96% of clusters are in from-clusters AND to-clusters within 2.0km
Hence we will skip linking all neighbors beyond 7.5km

STEP11i: Linking neighborhood traversal clusters (populating the table: traversal_cluster_links_highorder2)

NOTE: Review settings at "STEP9a: Linking neighborhood shortcuts" step in PHASE5 -- as this step is doing similar linking operation

Config Params:
dijkstraL2NodeCacheSize is set to 2 million entries so that Dijkstra can run faster
batchedNodeAccessBatchSlots is set to -1 to disable batched MapData access -- as it is slow for light-weight forward-only
clusterEdgeFetchBatchSize is 1000 since linking traversal clusters is slow
secondaryCacheNodeSize can be increased well to 9437184 -- as this task is going to be search-only and on forward-only node-cache.
persistSecondaryCacheNodes is increased to 2097152 -- since node/edge fetched are for forward-only one-directional entities
Runs with defaultSearchMaxVisitedCount for skipped slow Dijkstra:
sqrt(100000) = 316; 316*10m (per edge distance) = 3.16km -- cap is applied since almost all links are < 4km

nohup ${PCH_APP_HOME}/run_G2KClusteredEdgeLinker.sh --action buildTraversalClusterLinksForwardHighOrder2 > $PCH_LOG_HOME/nohup.out 2>&1 &

WARNING start forward linking first -- as it truncates the traversal_cluster_links_highorder2 table at the first round.

NOTE:
Runs with defaultSearchMaxVisitedCount -- skipping from linking if Dijkstra reaches this visited count
The script will run for (TOTAL_NEAREST_TRAVERSAL_CLUSTERS/TOTAL_CLUSTER_EDGES_PER_BATCH)+1 times
It runs for ~6days

SELECT search_mode,COUNT(*) FROM traversal_cluster_nolink_highorder2 GROUP BY search_mode ORDER BY search_mode;
mode: 1: slow Dijkstra; 2: exceeded search limits; 3: Invalid
search_mode | count
-------------+-------
1 | 1996
2 | 665
3 | 1303
NOTE: 38345 out of 512795 (~7.5%) nearest clusters are not linked due to slow Dijkstra (mode 1)

nohup ${PCH_APP_HOME}/run_G2KClusteredEdgeLinker.sh --action buildTraversalClusterLinksBackwardHighOrder2 > $PCH_LOG_HOME/nohup.out 2>&1 &

WARNING complete forward linking first -- as it truncates the traversal_cluster_links_highorder2 table at the first round.

NOTE:
Runs for linking on reverse direction with defaultSearchMaxVisitedCount -- skipping from linking if Dijkstra reaches this visited count
The script will run for (TOTAL_NEAREST_TRAVERSAL_CLUSTERS/TOTAL_CLUSTER_EDGES_PER_BATCH)+1 times
It runs for ~4days

SELECT COUNT(*) FROM traversal_cluster_links_highorder2;

Results:
  count
---------
 2112635

Results:
  count
---------
 2112635

NOTE:
The links count should be close to total clusters * nearestClusteredShortcutsToLink by ~90%

Link all slow Dijkstra exclusions:

Config Params:
executorThreads is increased since this task is more DB bound
maxSearchMaxVisitedCount is set to large value, 350000 that will get applied when fixDefaultSearches argument is set (as below)
sqrt(350000) = 591; 591*10m (per edge distance) = 5.9km -- cap is applied if search has navigated around 6 and didn't find solution
6km is selected since longest link was 2.3km
Runs with defaultSearchMaxVisitedCount -- skipped from linking if Dijkstra reaches this visited count
work_mem, graphDBPoolSize, executorThreads are all increased to make too many threads to work -- since performance of "fixDefaultSearches" task is going to be bound by DB reads
secondaryCacheNodeSize is reduced to avoid memory related failures
OPTIONAL: These two tasks are going to work slow with low cache performance. Hence they can be OPTIONALLY run with low executorThreads and secondaryCacheNodeSize

nohup ${PCH_APP_HOME}/run_G2KClusteredEdgeLinker.sh --action buildTraversalClusterLinksForwardHighOrder2 --fixDefaultSearches true > $PCH_LOG_HOME/nohup.out 2>&1 &
nohup ${PCH_APP_HOME}/run_G2KClusteredEdgeLinker.sh --action buildTraversalClusterLinksBackwardHighOrder2 --fixDefaultSearches true > $PCH_LOG_HOME/nohup.out 2>&1 &

NOTE:
Runs with fixDefaultSearches switch that applies defaultSearchMaxVisitedCount -- skipped from linking if Dijkstra reaches this visited count
Each command runs for ~2days each

SELECT COUNT(*) FROM traversal_cluster_links_highorder2;

Results:
  count
---------
 2112890

Results:
  count
---------
 2112890

SELECT COUNT(DISTINCT(from_cluster_id)) AS from_cluster_cnt, COUNT(DISTINCT(to_cluster_id)) AS to_cluster_cnt FROM traversal_cluster_links_highorder2;

Results:
 from_cluster_cnt | to_cluster_cnt
------------------+----------------
           294936 |         294204

Results:
 from_cluster_cnt | to_cluster_cnt
------------------+----------------
           294936 |         294204

SELECT COUNT(DISTINCT(from_cluster_id)) AS from_cluster_cnt, COUNT(DISTINCT(to_cluster_id)) AS to_cluster_cnt FROM nearest_traversal_clusters_highorder2;

 from_cluster_cnt | to_cluster_cnt
------------------+----------------
           271351 |         294644

 from_cluster_cnt | to_cluster_cnt
------------------+----------------
           271351 |         294644

WARNING The from-cluster count AND to-cluster count should be more than 90%. Else, review the logs for missed batch
(271351/295515) 91.82% (294644/295515) 99.7%

SELECT search_mode,COUNT(*) FROM traversal_cluster_nolink_highorder2 GROUP BY search_mode ORDER BY search_mode;
mode: 1: slow Dijkstra; 2: exceeded search limits; 3: Invalid
search_mode | count
-------------+-------
1 | 1793
2 | 677
3 | 1557
NOTE:
2045 slow-dijkstra has been slowly solved

Linking all zero-distance links:
Since large number of clusters overlap, there would be large number of from-clusters and to-clusters having common from-and-to nodes
We will add links between all such nodes -- to enable more routing paths at zero-cost
SELECT COUNT(*) FROM traversal_cluster_links_highorder2;

Results:
 count
--------
 2112890

Results:
 count
--------
 2112890

SET statement_timeout = 9600000; SET lock_timeout=1200000; SET work_mem TO '2048MB';
SELECT 0.0075 AS overlap_dist_tolerence \gset
CALL g2k_add_null_traversal_cluster_links_highorder2(0, 25, :overlap_dist_tolerence);
CALL g2k_add_null_traversal_cluster_links_highorder2(25, 50, :overlap_dist_tolerence);
CALL g2k_add_null_traversal_cluster_links_highorder2(50, 75, :overlap_dist_tolerence);
CALL g2k_add_null_traversal_cluster_links_highorder2(75, 100, :overlap_dist_tolerence);

NOTE:
overlap_dist_tolerence as 0.0075 means that the zero-distance nodes of source and destination clusters within 0.75km are grouped together
And only one traversal_cluster_link per each such group will be added -- NOT for all nodes
You can parallelize using multiple sessions

SELECT COUNT(*) FROM traversal_cluster_links_highorder2;

Results:
  count
---------
 3556666

Results:
  count
---------
 3556666

SELECT COUNT(DISTINCT(from_cluster_id)) AS from_cluster_cnt, COUNT(DISTINCT(to_cluster_id)) AS to_cluster_cnt FROM nearest_traversal_clusters_highorder2;

from_cluster_cnt | to_cluster_cnt
------------------+----------------
           271351 |         294644


from_cluster_cnt | to_cluster_cnt
------------------+----------------
           271351 |         294644

WARNING The from-cluster count AND to-cluster count should be more than 95%. Else, review the logs for missed batch
(271351/295515) 91.82% (294644/295515) 99.7%

STEP11j1: Populating traversal_cluster_links distances
SET statement_timeout = 9600000; SET lock_timeout=1200000; SET work_mem TO '2048MB';
CALL g2k_update_traversal_cluster_links_distance_highorder2(0, 25);
CALL g2k_update_traversal_cluster_links_distance_highorder2(25, 50);
CALL g2k_update_traversal_cluster_links_distance_highorder2(50, 75);
CALL g2k_update_traversal_cluster_links_distance_highorder2(75, 100);

NOTE:
You can parallelize using multiple sessions

SELECT MIN(distance), MAX(distance) FROM traversal_cluster_links_highorder2;

Results:
 min |         max
-----+---------------------
   0 | 0.19749963795270298

Results:
 min |         max
-----+---------------------
   0 | 0.19749963795270298

NOTE: longest traversal_cluster_link is 19.75km

Remove Very bad links:
SELECT link_edge_id, edge_cost,distance, from_node_pt<->to_node_pt as crow_distance
FROM traversal_cluster_links_highorder2 ORDER BY distance DESC LIMIT 10;

If distance > 5*crow_distance, then delete them
DELETE FROM traversal_cluster_links_highorder2 WHERE distance > 0.10;
<<DELETE 98>>

SELECT MIN(distance), MAX(distance) FROM traversal_cluster_links_highorder2;

Results:

Results:
 min |         max
-----+---------------------
   0 | 0.09984103385404404

STEP11j2: Including traversal_cluster_links to 2nd level nodes/edges

For comparison before-and-after:
SET statement_timeout=3600000;
SELECT MIN(CASE WHEN edges_from_ids IS NULL THEN 0 ELSE cardinality(edges_from_ids) END), MAX(cardinality(edges_from_ids)), MIN(CASE WHEN edges_to_ids IS NULL THEN 0 ELSE cardinality(edges_to_ids) END), MAX(cardinality(edges_to_ids)) FROM node_highorder2;

Results:
 min | max | min | max
-----+-----+-----+-----
   0 |  76 |   0 |  56

Results:
 min | max | min | max
-----+-----+-----+-----
   0 |  76 |   0 |  56

SET statement_timeout = 9600000; SET lock_timeout=1200000; SET work_mem TO '2048MB';
-- WARNING: Do not parallelize -- as it will cause ShareLock issues
CALL g2k_enhance_graph_by_traversal_cluster_links_highorder2(0, 25);
CALL g2k_enhance_graph_by_traversal_cluster_links_highorder2(25, 50);
CALL g2k_enhance_graph_by_traversal_cluster_links_highorder2(50, 75);
CALL g2k_enhance_graph_by_traversal_cluster_links_highorder2(75, 100);
-- WARNING: Do not parallelize -- as it will cause ShareLock issues

NOTE: On DEV, it completes in 5min; On PROD in 20min

Comparing graph improvements
SELECT MIN(CASE WHEN edges_from_ids IS NULL THEN 0 ELSE cardinality(edges_from_ids) END), MAX(cardinality(edges_from_ids)), MIN(CASE WHEN edges_to_ids IS NULL THEN 0 ELSE cardinality(edges_to_ids) END), MAX(cardinality(edges_to_ids)) FROM node_highorder2;

Results:
 min | max | min | max
-----+-----+-----+-----
   0 | 787 |   0 | 785

Results:
 min | max | min | max
-----+-----+-----+-----
   0 | 787 |   0 | 785

<<Should be more or same to before>>

STEP11k: Check reachability

nohup ${PCH_APP_HOME}/run_G2KGraphAnalyzer.sh --action graphAnalyzerCheckNodeReachabilityHighOrder2 --randomSeed 12345 > $PCH_LOG_HOME/nohup.out 2>&1 &

This will pick random nodes and reach all other nodes in forward and backward directions.
All random nodes should be able to cover entire graph (fully reachable to everyone)

On PROD:
[G2KGraphAnalyzer] checkGraphReachability: Total forward nodes that could reach all nodes: 0 maxReachablePct: 0.051% minReachablePct: 0.000% out of 10 tries
[G2KGraphAnalyzer] checkGraphReachability: Total backward nodes that could reach all nodes: 0 maxReachablePct: 0.072% minReachablePct: 0.000% out of 10 tries
[G2KGraphAnalyzer] checkGraphReachability: Total nodes that could reach all nodes: 0 maxReachablePct: 0.072% minReachablePct: 0.000% out of 10 tries

NOTE: Max reachability is 0.051% forward and 0.072% backward

The result of clusters linked is:

Ref: C:\GangaToKaveri\docs\g2k_on_osm_line_with_island_clusters_linked.png

Ref: C:\GangaToKaveri\docs\g2k_large_clusters_linked_05172025.png
NOTE: links are in pink/red color

~~~~~ Take FULL DB backup ~~~~~